var sortArray = function (nums) {
  console.time("快速排序耗时");
  const N = nums.length;
  quickSort(nums, 0, N - 1);
  console.timeEnd("快速排序耗时");
  return nums;
};

function quickSort(nums, left, right) {
  if (left >= right) {
    return;
  }
  let pIndex = partition(nums, left, right);
  quickSort(nums, left, pIndex - 1);
  quickSort(nums, pIndex + 1, right);
}

function partition(nums, left, right) {
  let pivot = nums[left];
  let i = left + 1;
  let j = right;
  while (true) {
    while (i <= right && nums[i] <= pivot) {
      i++;
    }
    while (j > left && nums[j] > pivot) {
      j--;
    }
    if (i >= j) {
      break;
    }
    swap(nums, i, j);
    i++;
    j--;
  }
  swap(nums, left, j);
  return j;
}

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

let arr = sortArray([6, 9, 0, 4, 8, 3, 2, 7, 1, 5]);
console.log(arr);
